package Tu.Linjiejuzhen;

import Queue.LinkedQueue;
import stack.LinkedStack;

import java.util.ArrayList;

/**
 * Created by Administrator on 2017/11/20/020.
 */
public class Linjie {
    ArrayList vertices = new ArrayList();//存放结点的集合
    int[][] edges; //邻接矩阵的二维数组
    int NumEdges; //边的数量
    int[] isTrav;            //遍历标志
    static final int MaxValue=65535;

    public Linjie(int n)
    {
        edges = new int[n][n];
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(i==j) //对角线上的元素为0
                {
                    edges[i][j]=0;
                }
                else
                {
                    edges[i][j]=-1;
                }
            }
        }
        NumEdges = 0;
    }

    //返回边的数量
    public int getNumEdges()
    {
        return this.NumEdges;
    }

    //返回结点的数量
    public int getNumOfVertice()
    {
        return vertices.size();
    }

    //返回结点的值
    public Object getValueOfVertice(int index)
    {
        return this.vertices.get(index);
    }

    //获得某条边的权值
    public int getWeightOfEdges(int v1,int v2) throws Exception
    {
        if((v1 < 0 || v1 >= vertices.size())||(v2 < 0||v2 >= vertices.size()))
        {
            throw new Exception("v1或者v2参数越界错误！");
        }
        return this.edges[v1][v2];

    }

    //插入结点
    public boolean insertVertice(Object obj)
    {
        return vertices.add(obj);
    }
    public boolean removeVertice(Object obj){
        return vertices.remove(obj);
    }

    //插入带权值的边
    public boolean insertEdges(int v1,int v2,int weight) throws Exception
    {
        boolean result = false;
        if((v1 < 0 || v1 >= vertices.size())||(v2 < 0||v2 >= vertices.size()))
        {
            throw new Exception("v1或者v2参数越界错误！");
        }

        this.edges[v1][v2]=weight;
        this.NumEdges++;
        result = true;
        return result;
    }

    //删除某条边
    public void removeEdges(int v1,int v2) throws Exception
    {
        if((v1 < 0 || v1 >= vertices.size())||(v2 < 0||v2 >= vertices.size()))
        {
            throw new Exception("v1或者v2参数越界错误！");
        }
        if( v1==v2 || this.edges[v1][v2]==-1)//自己到自己的边或者边不存在则不用删除。
        {
            throw new Exception("边不存在！");
        }

        this.edges[v1][v2]=-1;
        this.NumEdges--;
    }

    //打印邻接矩阵
    public void ToString()
    {
        for(int i=0;i<this.edges.length;i++ )
        {
            for(int j=0;j<this.edges[i].length;j++)
            {
                System.out.print(edges[i][j]+" ");
            }
            System.out.println();
        }
    }
    //判断图是否为空
    public boolean isEmpty(Linjie g){
       return (vertices.size()==0);
    }

    public static void DeepTraOne(Linjie g,int n){//从第n个节点开始遍历
        g.isTrav[n] = 1;              //标记为1表示该顶点已经被处理过
        System.out.println("—>" + g.vertices.get(n)); //输出节点数据
        //添加处理节点的操作
        for(int i = 0;i<g.vertices.size();i++)
        {
            if(g.edges[n][i] != Linjie.MaxValue && g.isTrav[i] == 0)
            {
                DeepTraOne(g, i);     //递归进行遍历
            }
        }
    }
    public static void  DeepTraGraph(Linjie g) {
        int[] isTrav = new int[100];            //遍历标志
        for (int i = 0; i < g.vertices.size(); i++) {
            g.isTrav[i] = 0;
        }
        System.out.println("深度优先遍历：");
        for (int i = 0; i < g.vertices.size(); i++) {
            if (g.isTrav[i] == 0)
                DeepTraOne(g, i);
        }
        System.out.println();
    }

     public ArrayList iteratorBFS(int start) throws Exception {
        int currentVertex;
        int next = -1;
        LinkedQueue<Integer> traversalQueue = new LinkedQueue<Integer>();
        ArrayList iter = new ArrayList<>();
        boolean[] visited = new boolean[vertices.size()];
        for (int i = 0; i < visited.length; i++)
            visited[i] = false;
        traversalQueue.enqueue(start);
        visited[start] = true;

        while (!traversalQueue.isEmpty()) {
            currentVertex = traversalQueue.dequeue();
            iter.add(vertices.get(currentVertex));
            for (int j = 0; j < visited.length; j++) {
                if (edges[currentVertex][j]!=0&&edges[currentVertex][j]!=-1 && !visited[j]) {
                    traversalQueue.enqueue(j);
                    visited[j] = true;
                }
            }
        }
        return iter;
    }
    public ArrayList iteratorDFS(int start) throws Exception{
        int currentVertex;
        int next = -1;
        LinkedStack<Integer> traversalStack = new LinkedStack<Integer>();
        ArrayList iter = new ArrayList<>();
        boolean[] visited = new boolean[vertices.size()];
        boolean found;
        for (int i = 0; i < visited.length; i++)
            visited[i] = false;
        traversalStack.push(start);
        iter.add(vertices.get(start));
        visited[start] = true;

        while (!traversalStack.isEmpty()) {
            currentVertex = traversalStack.peek();
            found = false;
            for (int j = 0; j < visited.length&& !found; j++) {
                if (edges[currentVertex][j]!=0&&edges[currentVertex][j]!=-1 && !visited[j]) {
                    traversalStack.push(j);
                    iter.add(vertices.get(j));
                    visited[j] = true;
                    found  = true;
                }
                if(!found && !traversalStack.isEmpty())
                    traversalStack.pop();
            }
        }
        return iter;
    }
}
